/*
题目链接：https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/description/
600. 不含连续1的非负整数-困难
完成日期：2024/10/4
数位DP
*/
class Solution {
public:
    int a[30];
    long long dp[30][2];
    long long dfs(int po,int l,int pr){
        if(po==-1){
            return 1;
        }
        if(!l&&dp[po][pr]!=-1) return dp[po][pr];
        int u=l?a[po]:1;
        int ans=0;
        for(int i=0;i<=u;++i){
            if(pr&&i==1) continue;
            ans+=dfs(po-1,l&&i==u,i);
        }
        if(!l)dp[po][pr]=ans;
        return ans;
    }
    long long solve(int x){
        int pos=0;
        while(x){
            a[pos++]=x%2;
            x/=2;
        }
        return dfs(pos-1,1,0);
    }
    int findIntegers(int n) {
        memset(dp,-1,sizeof dp);
        return solve(n);
    }
};